Tỉnh An Xuyên được thành lập trên cơ sở đổi tên tỉnh Cà Mau theo Sắc lệnh số 143-NV để thay đổi địa giới và tên Đô thành Sài Gòn – Chợ Lớn cùng các tỉnh và tỉnh lỵ tại Việt Nam. Địa giới và địa danh các tỉnh ở miền Nam thay đổi nhiều, một số tỉnh mới được thành lập. Theo Sắc lệnh này, địa phận Nam Phần của Việt Nam Cộng Hoà gồm Đô thành Sài Gòn và 22 tỉnh. Lúc này, tỉnh Cà Mau được đặt tên mới là tỉnh An Xuyên, còn tỉnh lỵ đổi tên là Quản Long. An Xuyên chính là tên của làng sở tại trước kia thuộc tổng Quản Long, vốn là nơi đặt quận lỵ quận Cà Mau trước năm 1956. Đồng thời, xã An Xuyên cũng được đổi tên thành xã Tân Xuyên thuộc quận Quản Long và là nơi đặt tỉnh lỵ Quản Long của tỉnh An Xuyên.

Ngày 5 tháng 8 năm 1957, tỉnh An Xuyên bao gồm 6 quận, 23 xã:

• Quận Quản Long gồm 4 xã; quận lỵ: Quản Long
• Quận Cái Nước gồm 6 xã; quận lỵ: Cái Nước Ngọn
• Quận Đầm Dơi gồm 4 xã; quận lỵ: Tân Duyệt
• Quận Thới Bình gồm 4 xã; quận lỵ: Thới Bình
• Quận Năm Căn gồm 2 xã; quận lỵ: Năm Căn
• Quận Sông Ông Đốc gồm 3 xã; quận lỵ: cửa sông Ông Đốc.

Tuy nhiên, chính quyền Mặt trận Dân tộc Giải phóng Miền Nam Việt Nam và sau này là Chính phủ Cách mạng lâm thời Cộng hòa Miền Nam Việt Nam cùng với Việt Nam Dân chủ Cộng hòa không công nhận tên gọi này mà vẫn gọi theo tên cũ là tỉnh Cà Mau.

Tháng 2 năm 1976, tỉnh An Xuyên (tức tỉnh Cà Mau) được sáp nhập với tỉnh Bạc Liêu thành tỉnh Minh Hải.

Cuối năm 1996, tỉnh Minh Hải được chia lại thành tỉnh Cà Mau và tỉnh Bạc Liêu như cũ.

Địa bàn tỉnh An Xuyên cũ hiện nay tương ứng với hầu như toàn bộ diện tích tỉnh Cà Mau ngày nay; ngoại trừ địa bàn xã Khánh Thuận thuộc huyện U Minh và hai xã Biển Bạch, Tân Bằng thuộc huyện Thới Bình vốn trước năm 1975 lại cùng thuộc địa bàn xã Tân Bằng, quận Hiếu Lễ, tỉnh Kiên Giang của chính quyền Việt Nam Cộng hòa.